1. Field of the Invention
The present invention relates generally to a wireless personal area network (WPAN), and more particularly, to an apparatus and a method of establishing a route from a source node to a destination node in the WPAN based on a tree topology.
2. Description of the Related Art
In general, data is transmitted and received between a mobile element and a base station in a mobile communication system. That is, the mobile element and the base station directly transmit and receive data without passing along other nodes. In contrast, a wireless personal area network (WPAN) has been developed to interconnect devices within a very short range. The WPAN is an ad-hoc data communication system enabling multiple nodes to communicate with each other. A transmitting node included in the ad-hoc network transmits data to a receiving node via other nodes. If the receiving node is adjacent to the transmitting node, data can be directly transmitted between the nodes. Referring now to FIG. 1, data transmission is described according a conventional routing algorithm in relation to nodes configuring an ad-hoc network based on a tree topology.
The ad-hoc network of FIG. 1 includes at least two nodes. The nodes are classified into two categories. One category includes a node maintaining a routing table and referred to as “N+”. The other category includes a node without a routing table and referred to as “N−”.
A conventional method for building a route in the ad-hoc network including N+ and N− will be described below. Let a node A be a source node, and a node I be a destination node. The source node requests a route setup from the destination node. Thus, the node A, which is N+, checks whether its routing table contains a route information with respect to the destination node I. If not, the node A broadcasts a route request RREQ message to neighbor nodes to set a route to the node I at step S100. The node B, which is N+, looks up a route information on the destination node I of the received RREQ message in its routing table. If storing the route information, the node B replies with a route reply RREP message. If not storing the route information, node B creates a route information field into its routing table and broadcasts the RREQ message to neighbor nodes at steps S102 and S108. The node C, which is N+, also performs the same operations as the node B at steps S104 and S106.
Upon receiving the RREQ message broadcast from the node B, the node G, which is the N−, transmits a RREP message to the node B in reply to the RREQ message at step S128. According to the conventional algorithm, the N− in the ad-hoc network transmits the RREP message in reply to the RREQ message. The N−, although itself is not the destination node requested in the received RREQ message, transmits the RREP message according to the tree topology and its node characteristic. That is, since the N− does not have its routing table, the N− cannot store or look up the route information even after receiving the RREQ message, and since the tree topology only allows message transmission to an upstream node or a downstream node, further route search is not feasible. The RREP message from the node G is forwarded to the node A via the node B at step S120. In general, each node stores in its neighbor list information on nodes within a certain distance, such as, for example, 1 hop, at the creation phase of the tree topology.
The node D, which is the N−, performs the same operations as the node G. Hence, a RREP message generated by the node D is forwarded to the node A via the nodes C and B at steps S124, S122, and S120. Upon receiving the RREQ message from the node C, the node F, which is the N+, can broadcast the RREQ message at steps S110, S112 and S114. The node E performs the same operations as the node G. The node H forwards the received RREQ message to the node I at step S116. Upon receiving the RREQ message, the node I recognizes that a node for which the route is requested by the node A, is itself. Accordingly, the node I generates a RREP message in reply to the RREQ message. The RREP message is forwarded to the node A along the route of the RREQ message. As a result, the route is established between the node A and node I. Albeit not described, a N+ having the routing table creates a field on the destination node into its routing table by use of the received RREQ message information and transmits the received RREQ message to neighbor nodes. In general, the N+ updates and forwards a hop count to the neighbor nodes. A route having the smallest hop count is selected to be a route between the nodes. Afterwards, Ns+ receive the RREP message in reply to the RREQ message and manage their routing tables by filling field values of the routing tables which are created for the related nodes. In light of the foregoing, the node A receives multiple RREP messages in reply to the single RREQ message. Meanwhile, the RREP messages from the Ns− are not necessary.
FIG. 2 illustrates another exemplary process for setting a route using nodes in the ad-hoc network based on the conventional algorithm, in which the forward route from the source node to the destination node can be established differently from the backward route from the destination node to the source node.
The node A requests to set up a route to the node E. The node A determines whether a route to the node E is established by looking up a stored routing table. As it is determined that there is no route to the node E, the node A broadcasts a RREQ message at step S200. Upon receiving the RREQ message, the node B also looks up a stored routing table and determines whether a route to the node E is set. As it is determined that there is no route to the node E, the node B broadcasts the RREQ message at step S202.
The node C determines whether itself is a node for which a route is requested by the node A. Since the node C is not the node for the route requested by the node A, the node C, which is the N−, transmits the RREQ message to the node D along a tree route at step S204. The node D also determines whether itself is a node for which a route is requested by the node A. Since the node D is not the node for the route requested by the node A, the node D transmits the RREQ message to the node E at step S206. The node E recognizes that itself is the node for the route requested by the node A.
The node E generates a RREP message in reply to the RREQ message. The generated RREP message is transmitted to the node D at step S210. The node D transmits the received RREP message to the node F at step S212. The node F forwards the RREP message to the source node A along the tree route. As a result, the forward route differs from the backward route, and a solution to this problem is required.